typedef int KeyType;
typedef	struct SPNode{
	KeyType key;
	struct SPNode *lchild, *rchild;
}SPNode, *Splay;

void RightRotate(Splay &T){
	Splay p = T->lchild;
	T->lchild = p->rchild; p->rchild = T;
	T = p;
}

void LeftRotate(Splay &T){
	Splay p = T->rchild;
	T->rchild = p->lchild; p->lchild = T;
	T = p;
}

void Splay(Splay &T, KeyType key){
	SPNode N;
	N.lchild = N.rchild = NULL;
	Splay ltree, rtree; ltree = rtree = &N;
	while (T->key != key){
		if (T->key > key){
			if (T->lchild && T->lchild->key > key){
				RightRotate(T);
			}
			else if (!T->lchild) break;
			rtree->lchild = T; rtree = T; T = T->lchild;
		}
		else {
			if (T->rchild && T->rchild->key < key){
				LeftRotate(T);
			}
			else if (!T->rchild) break;
			ltree->rchild = T; ltree = T; T = T->rchild;
		}
	}
	ltree->rchild = T->lchild; rtree->lchild = T->rchild;
	T->rchild = N.lchild; T->lchild = N.rchild;
}

Splay SearchSplay(Splay &T, KeyType key){
	if (!T) return NULL;
	Splay(T, key);
	else return T;
}

Splay DeleteSplay(Splay &T, KeyType key){
	Splay p;
	if (!(p = SearchSplay(T, key)))return NULL;
	if (p->key == key){
	 	Splay q = SearchSplay(p->lchild, key + 1);
	 	q->rchild = p->rchild;
	 	p->lchild = p->rchild = NULL;
	 	T = q;
	 }
	 return NULL;
}

Splay InsertSplay(Splay &T, KeyType key){
	Splay p;
	if (!(p = SearchSPlay(T, key))){
		if (p->key == key) return T;
		Splay q = (Splay)malloc(sizeof(SPNode));
		q->key = key;
		if (p->key < key){
			q->lchild = p; q->rchild = p->rchild;
		}
		else {
			q->rchild = p; q->lchild = p->lchild;
		}
		T = q;
	}
	return T;
}

Splay PredecessorSplay(Splay &T, KeyType key){
	Splay p = SearchSplay(T, key);
	if (p && p->lchild){
		return SearchSplay(p->lchild, key + 1);
	}
	return NULL;
}

Splay SuccessorSplay(Splay &T, KeyType key){
	Splay p = SearchSplay(T, key);
	if (p && p->rchild){
		return SearchSplay(p->rchild, key + 1);
	}
	return NULL;
}
//Split
Splay SplitSplay(Splay &T, Splay &S1, Splay &S2, KeyType key){
	if (!T) return T;
	Splay p = SearchSplay(T, key);
	if (p->key == key){
		S1 = p->lchild; S2 = p->rchild;
		return p;
	}
	else return NULL;
}
//Merge
Splay MergeSplay(Splay &S1, Splay &S2){
	if (!S1 && !S2) return NULL;
	else if (S1 && !S2) return S1;
	else if (!S1 && S2) return S2;
	else {
		FindMaxKey(S1);
		S1->rchild = S2; return S1;
	}
}
//FindMaxKey
KeyType FindMaxKey(Splay &T){
	// SPNode N; N.lchild = N.rchild = NULL;
	// Splay p = T, ltree = &N;
	Splay p = T, ltree = NULL;
	while (p->rchild){
		// ltree->rchild = p; ltree = p;
		ltree = p;
		p = p->rchild;
	}
	ltree->rchild = p->lchild; p->lchild = T;
	// p->lchild = N.rchild;
	T = p;
	return p->key;
}
//FindMinKey
KeyType FindMinKey(Splay &T){
	// SPNode N; N.lchild = N.rchild = NULL;
	// Splay p = T, rtree = &N;
	Splay p = T, rtree = NULL;
	while (p->lchild){
		// rtree->lchild = p; rtree = p;
		rtree = p;
		p = p->lchild;
	}
	rtree->lchild = p->rchild; p->rchild = T;
	// p->rchild = N.lchild;
	T = p;
	return p->key;
}
//Rank
int RankSplay(Splay &T, KeyType key){
	Splay p;
	if ((p = SearchSplay(T, key)) && p->key == key){
		return CountSplay(p->lchild) + 1;
	}
	else return 0;
}
int CountSplay(Splay T){
	if (T){
		return CountSplay(T->lchild) + CountSplay(T->rchild) + 1;
	}
	else return 0;
}